package Offer869;

import java.util.Arrays;


/**
 * 重新排序得到2的幂
 * 给定正整数 N，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
 * <p>
 * 如果我们可以通过上述方式得到2 的幂，返回 true；否则，返回 false。
 *
 * @author 23737
 * @time 2021.10.28
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().isTwo(1024));
        System.out.println(new Solution().reorderedPowerOf2(1042));
    }
}

/**
 * 个人解法
 * 回溯
 */
class Solution {
    public boolean reorderedPowerOf2(int n) {
        //首先将数字转为一个字符数组
        char[] chars = String.valueOf(n).toCharArray();
        //对字符数组排序
        Arrays.sort(chars);
        //遍历，但是注意I的增长是每次乘以2
        for (int i = 1; i <= 1e9 ; i*=2) {
            //将i转为字符数组
            char[] temp = String.valueOf(i).toCharArray();
            //进行排序
            Arrays.sort(temp);
            //进行两个排序后的字符数组的比较，如果相同就返回true
            if (Arrays.equals(chars,temp)) return true;
        }
        //遍历完还没返回说明没有找到，返回false
        return false;
    }

    //客串一下：判断一个数是否为2的幂的高阶方法（位运算）
    public boolean isTwo(int n){
        return (n>0)&&(n&(n-1))==0;
    }
}
